Threads are portions of code which can, at least for a time, be run independently of one another, and which can be run concurrently or in parallel with one another. Concurrency refers to the case where threads are interleaved with one another through the same execution unit of a processor, thus providing an effectively simultaneous form of execution. Parallelism refers to the case where threads are executed truly simultaneously through different parallel execution units of the same processor. In a given program or set of programs, two or more threads of the program may be run concurrently and/or in parallel at any one time, depending on the resources of the system.
Threads can take the form of hardware threads or software threads. In the case of hardware threads, the processor itself comprises hardware support for each thread, at least in the form a set of context registers for each of the threads that can be run concurrently or in parallel at any one time. Each set of context registers stores a program state of a respective thread, such as the program counter and operands. In the case of software threads, the concurrency or parallelism is achieved not (or not only) though hardware support for each thread, but rather the thread states are maintained at a higher level in software. Either way, in many cases the threads may be scheduled for execution by the operating system running on the computer system. The threads in question may comprise threads of the operating system itself or threads of one or more applications run on the operating system.
One task which a thread may perform is memory allocation and deallocation. Typically the operating system comprises a memory page table which maps a physical memory space of one or more physical memory devices to a virtual address space. From amongst this virtual address space, a software process can allocate one or more blocks of memory to be made available to the software for performing a particular task or tasks. Metadata is associated with the virtual address space in order to record which blocks are currently allocated. The data structure comprising the virtual memory space and the metadata is sometimes referred to as the “arena”. When blocks of the virtual memory space are no longer needed, the software should make sure it de-allocates the blocks to be made available for other tasks.
In a multi-threaded program or set of programs, each thread may comprise its own instance of a memory allocator for allocating and deallocating blocks of memory. This results in contention, i.e. competition for the same resource (the metadata). This contention needs to be resolved since only one thread should be allowed to manipulate the metadata at any one time. To achieve this, conventional techniques use a system of “locks”, whereby when a thread is accessing the arena to change the metadata, it acquires a lock on the metadata to prevent any other threads manipulating the metadata at the same time.